MPRI 1.24 - Algorithmes randomisés (Cours n°12 Partie C/C) - Nicolas Schabanel (CNRS, LIAFA) <br /> <br />Lecture 2: Thursday Jan 30, 8:45-11:45 - Approximation algorithms & Randomized Rounding <br />• Random solution for Max-SAT <br />• Linear program relaxation for Max-Sat and its randomized rounding <br />• Mixing both algorithms yields a better one <br /> <br />Exercise session 2: Randomized rounding <br />• A semi-definite program for Max-Cut and the random cut by a hyperplane <br />• Randomized rounding of a linear program relaxation for Set-Cover <br /> <br />URL: https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-1-24
